The present application relates to data networking and more particularly to systems and methods for rerouting around failed links and/or nodes.
In the following, “link” generally refers to a network cable and/or connecting interface, and “node” generally refers to a router, switch or other network device connected to other nodes by links.
The Internet and IP networks in general have become key enablers to a broad range of business, government, and personal activities. More and more, the Internet is being relied upon as a general information appliance, business communication tool, entertainment source, and as a substitute for traditional telephone networks and broadcast media. As the Internet expands its role, users become more and more dependent on uninterrupted access.
To assure rapid recovery in the event of failure of a network link or node, so-called “Fast Reroute” techniques have been developed. In a network employing Fast Reroute, traffic flowing through a failed link or node is rerouted through one or more preconfigured backup tunnels. Redirection of the impacted traffic occurs very quickly to minimize impact on the user experience, typically in tens of milliseconds.
These Fast Reroute techniques have been developed in the context of MPLS Traffic Engineering where traffic flows through label switched paths (LSPs). Typically, the overall network is configured such that traffic flows through guaranteed bandwidth end-to-end “primary” LSPs. It is also possible to establish short primary LSPs in a non-Traffic Engineering network, only for the purpose of taking advantage of Fast Reroute techniques (see above-referenced patent application entitled “MPLS Reroute Without Full Mesh Traffic Engineering.”)
In either case, when a link or node failure occurs, traffic affected by the failure is rerouted to the preconfigured backup tunnels. These backup tunnels are typically (but not necessarily) used only for a very short time since simultaneously with the rerouting through the backup tunnels, the head ends of all affected primary LSPs are notified of the failure. This causes the head ends to reroute the primary LSPs around the failures so that, if the rerouting is successful, the backup tunnels are no longer needed. It is generally assumed that the probability of multiple failures in such a short time is small, so each failure may be considered independently.
Under the independent failure assumption, link bandwidth available for backup tunnels may be shared between backup tunnels protecting different links or nodes. The techniques disclosed in U.S. patent application Ser. No. 10/038,259 make use of this assumption to allow available backup bandwidth to be shared among links or nodes to be protected while assuring that guaranteed bandwidth requirements continue to be met during Fast Reroute conditions.
During network operation, primary LSPs will be established and torn down. To avoid the need to constantly reconfigure backup tunnels in response to changes in primary LSPs, it is advantageous to configure the backup tunnel(s) protecting a network element to accommodate the maximum bandwidth reservable for primary LSPs using that element.
Consider a node to be protected. The traffic burden to be protected will consist of a set of “primary traffic flows.” Each primary traffic flow consists of primary LSPs that can cross the protected node via a pair of links, one link to the protected node and another link away from the protected node. One or more backup tunnels will be established to protect each such link pair. Each backup tunnel consists of a sequence of one or more links defining the sequence of links it traverses. For each link, the total traffic burden of the primary traffic flows protected by backup tunnels that include (i.e. traverse) the link should not exceed the reservable backup bandwidth of the link.
It is thus necessary to identify a maximum primary traffic bandwidth for aggregates of primary traffic flows. A straightforward approach is to simply take the sum of the bandwidths of individual flows in the aggregate. As will be shown herein, however, this approach often results in an inflated estimate of the aggregate bandwidth to be protected by backup tunnels traversing a given link. The consequences of the exaggerated bandwidth estimates can include inefficient configuration of backup tunnels and even failure to find backup tunnels.
What is needed are improved systems and methods for estimating the total bandwidths of aggregates of primary traffic flows traversing a node to be protected.